/*
Date:20210521 1:00AM
key:先初始化成一个大数，最后是大数就返回-1.不能被组成的情况。
*/
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) 
    {
        int*dp=new int[amount+1];
        memset(dp,INT_MAX,amount+1);
        dp[0]=0;
        int Min;
        for(int i=1;i<amount+1;i++)
        {
            Min=INT_MAX;
            for(int&g:coins)
            {
                if(i-g>-1)
                {
                    Min=min(Min,dp[i-g]);
                }
            }
            if(Min==INT_MAX)
            {
                dp[i]=Min;
            }
            else
            {
                dp[i]=Min+1;
            }
            
        }
    if(dp[amount]==INT_MAX)
    {
        return -1;
    }
    else{return dp[amount];}
    }
};